package com.yuufa.test.graph;

/*
 * 約瑟夫問題:
 * 據說著名猶太曆史學家 Josephus有過以下的故事：
 * 在羅馬人佔領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，
 * 39個猶太人決定寧願死也不要被敵人抓到，於是決定了一個自殺方式，
 * 41個人排成一個圓圈，由第1個人 開始報數，每報數到第3人該人就必須自殺，
 * 然後再由下一個重新報數，直到所有人都自殺身亡為止
 */
public class Josephus {

    public static void main(String[] args) {
        int n = 41;
        int m = 3;
        int[] s = new int[n];
        int count = 0;
        int rear = 0;
        int i = 0;
        
        for(int k=0;k<n;k++) {
            s[k] = 0;
        }
        
        while(count < n) {
            
            do {
                if( s[rear] == 0) {
                    i++;
                }
                
                if(i == m) {
                    i = 0;
                    break;
                }
                
                rear = ( rear + 1 ) % n;
            } while(true);
            
            s[rear] = ++count;
        }
        
        for(int k=0;k<n;k++) {
            System.out.print(s[k] + " ");
        }
    }
}
